package com.leetcode;

import com.leetcode.common.ListNode;

import static com.leetcode.util.LinkedListUtil.createList;
import static com.leetcode.util.LinkedListUtil.printList;

/**
 * 86. 分隔链表
 * 双节点头指针
 */
public class Solution86 {

    public ListNode partition(ListNode head, int x) {
        ListNode cur = head;

        ListNode smallHead = new ListNode();
        ListNode bigHead = new ListNode();

        ListNode smallCur = smallHead;
        ListNode bigCur = bigHead;

        while (cur != null) {
            if (cur.val < x) {
                smallCur.next = cur;
                smallCur = smallCur.next;
            } else {
                bigCur.next = cur;
                bigCur = bigCur.next;
            }
            cur = cur.next;
        }
        bigCur.next = null;
        smallCur.next = bigHead.next;
        return smallHead.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 4, 3, 2, 5, 2};
        ListNode head = createList(nums);
        int x = 4;

        printList(head);

        ListNode newHead = new Solution86().partition(head, x);

        printList(newHead);
    }

}
